# from queue import PriorityQueue
# import time
#
# tic = time.time()
# import numpy as np

def fordijkstar(car,cross,road):
    # car_number = 1001
    # for_find_car = []
    # for i in range(len(car)):
    #     for_find_car.append(car[i][0])
    # car_index = for_find_car.index(car_number)

    class Vertex:
        #顶点类
        def __init__(self,vid,dist):
            self.vid = vid
            self.dist = dist

        def __lt__(self,other):
            return self.dist < other.dist

    class Vertex:
        #顶点类
        def __init__(self,vid,outList):
            self.vid = vid#出边
            self.outList = outList#出边指向的顶点id的列表，也可以理解为邻接表
            self.know = False#默认为假
            self.dist = float('inf')#s到该点的距离,默认为无穷大
            self.prev = 0#上一个顶点的id，默认为0
        def __eq__(self, other):
            if isinstance(other, self.__class__):
                return self.vid == other.vid
            else:
                return False
        def __hash__(self):
            return hash(self.vid)

    #存储边的权值
    edges = dict()
    def add_edge(front,back,value):
        edges[(front,back)]=value
    for edge_index in range(len(road)):
        add_edge(road[edge_index][4], road[edge_index][5], road[edge_index][1])
        if road[edge_index][6]==1:
            add_edge(road[edge_index][5], road[edge_index][4], road[edge_index][1])
    # # 存储边的权值
    # edges = dict()
    # def add_edge(front, back, value):
    #     edges[(front, back)] = value
    # for edge_index in range(len(road)):
    #     # speed_time = road[edge_index][1] / min(car[car_index][3], road[edge_index][2])
    #     add_edge(road[edge_index][4], road[edge_index][5],
    #              road[edge_index][1] / min(car[car_index][3], road[edge_index][2]))
    #     if road[edge_index][6] == 1:
    #         add_edge(road[edge_index][5], road[edge_index][4],
    #                  road[edge_index][1] / min(car[car_index][3], road[edge_index][2]))

    def get_unknown_min():#此函数则代替优先队列的出队操作
        the_min = 0
        the_index = 0
        j = 0
        for i in range(1,len(vlist)):
            if(vlist[i].know is True):
                continue
            else:
                if(j==0):
                    the_min = vlist[i].dist
                    the_index = i
                else:
                    if(vlist[i].dist < the_min):
                        the_min = vlist[i].dist
                        the_index = i
                j += 1
        #此时已经找到了未知的最小的元素是谁
        vset.remove(vlist[the_index])#相当于执行出队操作
        return vlist[the_index]

    def main(vlist_table_index):
        #将v1设为顶点
        vlist[vlist_table_index].dist = 0

        while(len(vset)!=0):
            v = get_unknown_min()
            # print(v.vid,v.dist,v.outList)
            v.know = True
            for w in v.outList:#w为索引
                if(vlist[int(w)].know is True):
                    continue
                if(vlist[int(w)].dist == float('inf')):
                    vlist[int(w)].dist = v.dist + edges[(v.vid,w)]
                    vlist[int(w)].prev = v.vid
                else:
                    if((v.dist + edges[(v.vid,w)])<vlist[int(w)].dist):
                        vlist[int(w)].dist = v.dist + edges[(v.vid,w)]
                        vlist[int(w)].prev = v.vid
                    else:#原路径长更小，没有必要更新
                        pass

    vlist_table = {}
    for vlist_table_index in range(len(cross)):
        # 创建一个长度为8的数组，来存储顶点，0索引元素不存
        vlist = [False]
        # 创建顶点对象
        for_find_road = []
        for i in range(len(road)):
            for_find_road.append(road[i][0])
        dic = {}
        for i in range(len(cross)):
            # for i in range(1):
            key1 = cross[i][0]
            key2 = []
            # value1 = []
            for j in range(4):
                if cross[i][j + 1] < 0:
                    continue
                location_road = for_find_road.index(cross[i][j + 1])
                if road[location_road][5] == key1:
                    if road[location_road][6] == 1:
                        key2.append(road[location_road][4])
                        # value1.append(road[location_road][1])
                    else:
                        continue
                else:
                    key2.append(road[location_road][5])
                    # value1.append(road[location_road][1])
            temp_dic = Vertex(key1, key2)
            vlist.append(temp_dic)
            temp_dic = []
            # temp_dic = dict(zip(key2,value1))
            # dic = dict(zip(key1,temp_dic))
            # dic[key1] = temp_dic
        # 使用set代替优先队列，选择set主要是因为set有方便的remove方法
        vset = set(vlist[1:])

        main(vlist_table_index+1)
        vlist_table[vlist_table_index+1] = vlist
        vlist = {}

    return vlist_table

# import scipy.io
# # data1 = scipy.io.loadmat('config.mat')
# data2 = scipy.io.loadmat('bianld.mat')
# # road = data1['Road']
# # car = data1['Car']
# # cross = data1['Cross']
# road = data2['road']
# car = data2['car']
# cross = data2['cross']
# vlist_table = fordijkstar(car,cross,road)
#
# def real_get_traj(vlist_table,start,index):
#     traj_list = []
#     def get_traj(index):#参数是顶点在vlist中的索引
#         if(index == start):#终点
#             traj_list.append(index)
#             print(traj_list[::-1])#反转list
#             return
#         if(vlist_table[start][int(index)].dist == float('inf')):
#             print('从起点到该顶点根本没有路径')
#             return
#         traj_list.append(index)
#         get_traj(vlist_table[start][int(index)].prev)
#     get_traj(index)
#     print('该最短路径的长度为',vlist_table[start][index].dist)
#
# real_get_traj(vlist_table,1,3)
# real_get_traj(vlist_table,6,3)

